/**
 * 剑指 Offer 14- I. 剪绳子
 * https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
 */

/**
 * @param {number} n
 * @return {number}
 */
function cuttingRope(n) {
  const dp = new Array(n + 1).fill(1);
  for (let i = 2; i <= n; i += 1) {
    const end = i >> 1;
    let max = 0;
    for (let j = 1; j <= end; j += 1) {
      max = Math.max(max, j * dp[i - j], j * (i - j));
    }
    dp[i] = max;
  }
  return dp[n];
}

console.log(cuttingRope(2) === 1);
console.log(cuttingRope(10) === 36);
